Subspace clustering refers to the problem of segmenting data drawn from aunion of subspaces. State-of-the-art approaches for solving this problem followa two-stage approach. In the first step, an affinity matrix is learned from thedata using sparse or low-rank minimization techniques. In the second step, thesegmentation is found by applying spectral clustering to this affinity. Whilethis approach has led to state-of-the-art results in many applications, it issub-optimal because it does not exploit the fact that the affinity and thesegmentation depend on each other. In this paper, we propose a jointoptimization framework --- Structured Sparse Subspace Clustering (S$^3$C) ---for learning both the affinity and the segmentation. The proposed S$^3$Cframework is based on expressing each data point as a structured sparse linearcombination of all other data points, where the structure is induced by a normthat depends on the unknown segmentation. Moreover, we extend the proposedS$^3$C framework into Constrained Structured Sparse Subspace Clustering(CS$^3$C) in which available partial side-information is incorporated into thestage of learning the affinity. We show that both the structured sparserepresentation and the segmentation can be found via a combination of analternating direction method of multipliers with spectral clustering.Experiments on a synthetic data set, the Extended Yale B data set, the Hopkins155 motion segmentation database, and three cancer data sets demonstrate theeffectiveness of our approach.
展开▼
